package experiment1.closestpoints;

public class ClosestPoints3 extends ClosestPoints{
    //分治法，已优化，min_dis = min{左区间最优解d1,有区间最优解d2},排除了 |points[i].x - points[mid].x| > mid_dis的情况，减少运算次数
    @Override
    public double solve(Point[] points, int l, int r) {
        if (l >= r) {
            return Double.MAX_VALUE;
        }
        int mid = (r + l) / 2;
        double d1 = solve(points, l, mid);
        double d2 = solve(points, mid + 1, r);
        double min = Math.min(d1, d2);
        return Math.min(min, crossMinDistance(points, l, mid, r,min));
    }


    public double crossMinDistance(Point[] points, int l, int mid, int r,double min) {
        double mid_dis = Double.MAX_VALUE;

        for (int i = mid; i >= l && Double.compare(points[mid].x - points[i].x,min) != 1;i--) {
            for (int j = mid + 1;j <= r && Double.compare(points[j].x-points[mid+1].x,min) != 1;j++){
                mid_dis = Math.min(mid_dis,points[i].distance(points[j]));
            }
        }
        return mid_dis;
    }
}
